#include<vector>
#include<iostream>
#include<algorithm>

using namespace std;


void heapify(vector<int>& vec, int size, int idx)
{
    int left= 2*idx+1;
    int right =2*idx+2;
    int max =idx;
    if(left<size&&vec[left]>vec[max]) max=left;

    if(right<size&&vec[right]>vec[max]) max=right;

    if(max!=idx) 
    {
        swap(vec[idx],vec[max]);
        heapify(vec, size, max);  //  注意此处需要传入size,保证heapify的正确性
    }

}

void heap_build(vector<int>& vec, int idx)
{
    int tmp= (idx-2)/2;

    for(;tmp>=0;tmp--)
    {
        heapify(vec,idx, tmp);
    }

}

void heap_sort(vector<int>& vec,int n)
{
    heap_build(vec,n);
    for(int i=0;i<n;++i)
    {
        swap(vec[0],vec[n-i-1]);
        heapify(vec,n-i-1,0);
    }

}

int main()
{
    vector<int> vec = {16, 4, 10, 14, 7, 9, 3, 2, 8, 1};

    heap_sort(vec, vec.size());

    for (int i = 0; i < vec.size(); ++i) {
        std::cout << vec[i] << " ";
    }

    return 0;
}
